Service-to-service authentication is typically performed utilizing digital signatures. For instance, a service digitally may digitally sign a message using its private cryptographic key and transmit this message to a recipient service. The recipient service may utilize the sending service's public cryptographic key or digital certificate to verify the authenticity of the received message. However, inter-service interactions are not usually isolated but instead follow a certain path that may encompass multiple services. Particularly, a service may be able to validate that it is receiving an authentic message from another service but may not be able to validate that the message has followed a certain path before reaching the sending service. Similarly, the sending service may only be able to validate that it is receiving an authentic response from the recipient service but may not be able to validate the path beyond the recipient service used to deliver the response.